Выпуклая оптимизация: принципы безусловной минимизации

Мы переходим от теоретического существования минимума к алгоритмическому механизму оптимизации. Наша основная цель — минимизировать $f(x)$ (9.1) где $f: \mathbf{R}^n \to \mathbf{R}$ выпукла и дважды непрерывно дифференцируема. Поскольку $f$ дифференцируема и выпукла, необходимым и достаточным условием для того, чтобы точка $x^*$ была оптимальной, является $\nabla f(x^*) = 0$.

Алгоритмическая структура

Численные решения строят последовательность минимизации: последовательность точек $x^{(0)}, x^{(1)}, \dots \in \text{dom } f$ с $f(x^{(k)}) \to p^*$ при $k \to \infty$. Каждый шаг обновляет положение по формуле $x^{(k+1)} = x^{(k)} + t^{(k)}\Delta x^{(k)}$, где $\Delta x$ — направление спуска.

Инициализация и сходимость

Методы, описанные в этой главе, требуют подходящей начальной точки $x^{(0)}$. Начальная точка должна лежать в $\text{dom } f$, а кроме того, подуровневое множество $S = \{x \in \text{dom } f \mid f(x) \le f(x^{(0)})\}$ должно быть замкнутым. Это гарантирует, что последовательность остается в хорошо поведающейся области, где гессиан предоставляет полезную информацию.

Направления спуска

Простейшим направлением является $\Delta x = -\nabla f(x)$. Однако эффективность часто требует учета различных геометрий через направление наискорейшего спуска:

Квадратичная норма: $\|z\|_P = (z^T P z)^{1/2} = \|P^{1/2}z\|_2$.
$L_\infty$ норма: $\Delta x_{\text{sd}} = \Delta x_{\text{nsd}} \|\nabla f(x)\|_\infty = - \frac{\partial f(x)}{\partial x_i} e_i$ (Метод координатного спуска).

Модели второго порядка и доверительные области

Метод Ньютона использует аппроксимацию Тейлора второго порядка: $$\hat{f}(x+v) = f(x) + \nabla f(x)^T v + \frac{1}{2} v^T \nabla^2 f(x) v$$ Эта квадратичная функция минимизируется при $v = \Delta x_{nt}$ (шаг Ньютона). Мы определяем доверительную область: множество $\{v \mid \|v\|_2 \le \gamma\}$. Параметр $\gamma$ отражает нашу уверенность в модели второго порядка. Когда модель точна, мы решаем направление по формуле $v = L^{-T}w = -L^{-T}L^{-1}P^T g$ в системах ККТ.

🎯 Основные принципы сходимости

Эффективность измеряется скоростью, с которой исчезает ошибка $f(x^{(k)}) - p^*$. Для сильно выпуклых функций, ошибка $f(x^{(k)}) - p^*$ стремится к нулю не медленнее, чем геометрическая прогрессия. В контексте итерационных численных методов это называется линейной сходимостью.

Оценка недостаточности: $p^* \geq f(x) + \lambda(x) + \log(1 - \lambda(x))$, верно при $\lambda(x) < 1$.
Сумма самосогласованности: Если $f_1, f_2$ самосогласованы, то $f_1 + f_2$ также самосогласована.
Разреженность гессиана: Эффективность достигается, если условие разреженности гессиана: $\nabla^2 f(x)_{ij} = 0$ при $|i-j| > k$ выполняется.

ВОПРОС 1

Какое условие является как необходимым, так и достаточным для того, чтобы $x^*$ было глобальным минимизатором дифференцируемой выпуклой функции?

$∇² f(x*) ≽ 0$

$∇ f(x*) = 0$

Подуровневое множество $S$ замкнуто

$f(x*) = p^*$

ВОПРОС 2

Что происходит с методом Ньютона, если применить преобразования координат (аффинная инвариантность)?

Путь к оптимуму изменяется значительно

Алгоритм становится только линейно сходящимся

Метод не зависит от линейных преобразований координат

Гессиан становится вырожденным

ВОПРОС 3

Когда оценка недостаточности $p^* \geq f(x) + \lambda(x) + \log(1 - \lambda(x))$ гарантированно является верной?

Только когда $\lambda(x) < 1$

Для любого $x \in \text{dom } f$

Только для квадратичных функций

Когда гессиан диагональный

ВОПРОС 4

Если $f_1$ и $f_2$ самосогласованы, то какой из следующих является самосогласованным?

$f_1 \cdot f_2$

$f_1 / f_2$

$f_1 + f_2$

$f_1 - f_2$

ВОПРОС 5

Какова характерная черта линейной сходимости в итерационных методах?

Ошибка достигает нуля ровно за $n$ шагов

Ошибка сходится к нулю не медленнее, чем геометрическая прогрессия

Гессиан постоянен

Шаг $t$ всегда равен 1

Вызов: минимизация дробных и невыпуклых функций

Аналитические методы для безусловных задач

В задачах безусловной оптимизации мы часто сталкиваемся со структурами, которые кажутся сложными, но поддаются стандартным принципам. Рассмотрим два конкретных случая: невыпуклую квадратичную функцию и дробно-линейную квадратичную функцию.

Вопрос 1

Рассмотрим $f(x) = (1/2)x^T Px + q^T x + r$. Докажите, что если $P$ не является положительно полуопределенной ($P \nsucceq 0$), то задача не ограничена снизу.

Модельный ответ:
Если $P \nsucceq 0$, существует собственный вектор $v$, такой что $Pv = λv$ при $λ < 0$. Пусть $x = tv$, где $t$ — скаляр.
Подставляя в целевую функцию: $f(tv) = (1/2)t^2(v^T Pv) + t(q^T v) + r = (1/2)λt^2 ||v||^2 + t(q^T v) + r$.
При $t \to ∞$ доминирует член $t^2$. Поскольку $λ < 0$, выражение $(1/2)λt^2 ||v||^2 \to -∞$. Следовательно, функция не ограничена снизу.

Вопрос 2

Минимизируйте $f(x) = \frac{\|Ax - b\|_2^2}{c^T x + d}$ на $\text{dom} f = \{x \mid c^T x + d > 0\}$. Выведите условие для минимизатора.

Модельный ответ:
Чтобы минимизировать $f(x)$, устанавливаем градиент $∇f(x) = 0$. Пусть $u = Ax - b$ и $v = c^T x + d$. Функция имеет вид $f = u^T u / v$.
Используя правило дифференцирования дроби: $∇f(x) = \frac{2 A^T(Ax - b)(c^T x + d) - \|Ax - b\|_2^2 c}{(c^T x + d)^2} = 0$.
Это приводит к условию стационарности: $2(c^T x + d)A^T(Ax - b) = \|Ax - b\|_2^2 c$. Его можно решить, сводя к системе линейных уравнений или выполняя поиск по одному скалярному параметру, представляющему значение целевой функции.